package _go

/*
86. 分隔链表
难度
中等

409

收藏

分享
切换为英文
接收动态
反馈
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。



示例 1：


输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]


提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

//主要思路 删除标记法   将符合的节点从原链表中删除 并记录到新的删除链表中 主要是要切割删除节点的next
func partition(head *ListNode, x int) *ListNode {
	if head == nil {
		return head
	}

	//删除列表
	delTmp := &ListNode{}
	resDel := delTmp
	//head的前驱节点
	pre := &ListNode{0, head}
	res := pre

	for pre.Next != nil {
		//符合条件直接删除 并记录
		if pre.Next.Val >= x {
			//记录删除节点
			delTmp.Next = pre.Next
			delTmp = delTmp.Next

			pre.Next = pre.Next.Next
			//断开原来的指针

			delTmp.Next = nil
		} else {
			pre = pre.Next
		}
	}
	//fmt.Printf("res %s del %s\n",res,resDel)
	if res.Next == nil {
		return resDel.Next
	} else {
		if resDel.Next == nil {
			return res.Next
		} else {
			pre.Next = resDel.Next
			return res.Next
		}
	}
}
